package com.huangyi;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 不同路径
    static class Solution {
        int m, n;
        int[][] memo;

        public int uniquePaths(int _m, int _n) {
            m = _m;
            n = _n;
            memo = new int[101][101];  // 1-indexed，开101避免越界
            for (int i = 0; i < memo.length; i++) {
                Arrays.fill(memo[i], -1);  // -1表示未计算
            }
            return unique(m, n);
        }

        public int unique(int si, int sj) {
            // 边界条件：到达起点
            if (si == 1 && sj == 1) return 1;

            // 越界：超出网格边界
            if (si == 0 || sj == 0) return 0;

            // 查表：已计算过
            if (memo[si][sj] != -1) return memo[si][sj];

            // 递推：当前位置路径数 = 上方路径数 + 左方路径数
            memo[si][sj] = unique(si - 1, sj) + unique(si, sj - 1);
            return memo[si][sj];
        }
    }

    // 最长递增子序列
    static class Solution2 {
        int n;
        int[][] memo;

        public int lengthOfLIS(int[] nums) {
            n = nums.length;
            memo = new int[n][n+1];  // prev可以取到n，所以是n+1
            for(int[] row : memo) {
                Arrays.fill(row, -1);  // 初始化为-1表示未计算
            }
            return dfs(nums, 0, n);  // 从位置0开始，prev=n表示还没选过元素
        }

        public int dfs(int[] nums, int pos, int prev){
            if(pos == n) return 0;  // 遍历结束，返回0
            if(memo[pos][prev] != -1) return memo[pos][prev];  // 已计算过

            // 不选当前元素
            int noTake = dfs(nums, pos+1, prev);

            // 选当前元素（需满足严格递增条件）
            int take = 0;
            if(prev == n || nums[pos] > nums[prev]){
                take = dfs(nums, pos+1, pos) + 1;
            }

            // 取最大值并记忆化
            memo[pos][prev] = Math.max(take, noTake);
            return memo[pos][prev];
        }
    }
}
